Implementing Priority Queues using Partially Ordered Trees.


What's a Partially Ordered Tree (POT)?

	a complete binary tree
	that obeys the POT order property




What's a Complete Binary Tree?

	all levels except the bottom are completely filled
	nodes at the bottom level are as far left as possible


Draw an example of a complete binary tree on the board.


What's the height of a complete binary tree?

	a tree with N nodes has height at most logN




What's the POT order property?

	for every node X
	the value of X's parent is <= the value of X

	the root has the smallest value
	the compare is reversed for a Max heap


Draw an example of a POT on the board.




How do you Insert into a POT?

	add an item at the next available location
	percolate up until the order is correct

How do you percolate up?

	compare an item with its parent
	swap if the parent is larger


Show the result of inserting 5, 2, 8, 3, 1, 9, 6, 4 into a POT on the board.


Classwork
You may work with a partner.
Show the result of inserting E, C, H, A, G, D, F, B into a POT.


What's the Big-Oh of Insert?

	O(log n) in the worst case
	O(1) in the average case




How do you DeleteMin from a POT?

	replace the root with the last item
	percolate down until the order is correct

How do you percolate down?

	compare an item with its smaller child
	swap if the parent is larger


Show the result of DeleteMin from a POT on the board.


Classwork
You may work with a partner.
Show the result of DeleteMin from the previous POT.


What's the Big-Oh of DeleteMin?

	O(log n) in the worst case
	O(log n) in the average case




What's a Binary Heap?

	an implementation of a POT using an array

How do you store a Tree in an array?

	store the nodes in level order
	the root is at A[1] (A[0] not used)
	the children of the root are at A[2] and A[3]
	works for a complete binary tree


Draw an example of a Binary Heap on the board.


Where can you find the children of the node at A[i]?

	the left child of the node at i is at 2i
	the right child of the node at i is at 2i+1

Where can you find the parent of the node at A[i]?

	the parent of the node at i is at i/2


Show the result of Insert into a Heap on the board.


Show the result of DeleteMin from a Heap on the board.




Explain the code for Insert.

    void insert( Comparable x ) {
        int hole = ++currentSize;
        array[ 0 ] = x;
        for( ; x.compareTo( array[ hole / 2 ] ) < 0; hole /= 2 )
            array[ hole ] = array[ hole / 2 ];
        array[ hole ] = x;
    }




Explain the code for DeleteMin.

    public Comparable deleteMin( ) {
        Comparable minItem = findMin( );
        array[ 1 ] = array[ currentSize-- ];
        percolateDown( 1 );
        return minItem;
    }
    private void percolateDown( int hole ) {
        int child;
        Comparable tmp = array[ hole ];
        for( ; hole * 2 <= currentSize; hole = child ) {
            child = hole * 2;
            if( child != currentSize &&
                    array[ child + 1 ].compareTo( array[ child ] ) < 0 )
                child++;
            if( array[ child ].compareTo( tmp ) < 0 )
                array[ hole ] = array[ child ];
            else
                break;
        }
        array[ hole ] = tmp;
    }